public class EditDistance {
    // 最短编辑距离
    // https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int editDistance (String str1, String str2) {
        // write code here
        str1 = " " + str1;
        str2 = " " + str2;
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        // dp[i][j]表示str1字符串[0,i]之间的子串和str2[0,j]之间的子串的最短编辑距离
        int[][] dp = new int[c1.length][c2.length];
        // 状态转移方程
        // 如果c1[i] == c2[j]，那么dp[i][j] = dp[i-1][j-1]
        // 如果c1[i] != c2[j],那么就需要进行操作，有下面六种操作方式
        // 1.删除str1字符串的第i个字符，那么dp[i][j] = dp[i-1][j] + 1
        // 2.删除str2字符串的第j个字符，那么dp[i][j] = dp[i][j-1] + 1
        // 3.在str1字符串的第i个位置之后添加str2的第j个字符，dp[i][j] = dp[i][j-1] + 1
        // 4.在str2字符串的第j个位置之后添加str1的第i个字符，dp[i][j] = dp[i-1][j] + 1
        // 5.更换str1字符串的第i个字符为str2字符串的第j个字符,dp[i][j] = dp[i-1][j-1]+1
        // 6.更换str2字符串的第j个字符为str1字符串的第i个字符，dp[i][j] = dp[i-1][j-1]+1
        // 上面的六种编辑发存在重复的情况，所以可以总结为三种情况
        // dp[i][j-1]+1 dp[i-1][j]+1 dp[i-1][j-1]+1
        for (int i = 1; i < c1.length; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j < c2.length; j++)
            dp[0][j] = j;
        for (int i = 1; i < c1.length; i++) {
            for (int j = 1; j < c2.length; j++) {
                if (c1[i] == c2[j]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[c1.length-1][c2.length-1];
    }

    public static void main(String[] args) {
        System.out.println(new EditDistance().editDistance("nowcoder", "new"));
    }
}
